——傅里叶变换在信息学竞赛中主要作用是利用卷积思想,化乘为加,快速计算多项式乘法。

我太蒟了,看了$F(x)$篇博文,还是没看懂。

关于多项式,有了$O(nlogn)$乘法,就有了全世(jia)界(tong)!

$update(2019.6.27):$更新了一些证明和式子。

$update(2019.10.28):$发现模板题时限缩小,开始修锅(去冗余)。

当年写这篇文章的时候比较菜(现在仍然很菜),所以讲的比较含混不清,现在更新和精简了一些内容,希望能对大家有所帮助~

源码删去了17KB,更新了9KB内容。

文章中的代码已经进一步优化,可以通过模板题。

由于文章前后内容有所变化,已将讨论区清空。

警告 : 本文对数学水平有一定要求,如果发现看不懂,可以先存着。

另外,如果你掌握和式的话,学习速度将会大幅度提高。

此外,由于前面的内容太掉逼格,建议水平高的选手直接跳到“单位根”。

1.线段树(或者基本分治)：题目

2.基本数论：题目

3.码力：题目

4.基本数学：题目

然后在你刷完这些题之后,发现题和下面的内容并没什么关系。

附上一句,这是$\color{purple}\textsf{省选}$内容哦！(然而并没有什么影响)

$\color{Black}\colorbox{lightgreen}{总结一下}$

这里不会满屏都是三角函数!!,没有$e^i$和什么欧拉定理!!

不需要你会高数,只要用过平面直角坐标系,就可以看。

这篇文章源码40KB,写的时候挑战洛谷Blog(浏览器)性能极限

FFT全称(Fast Fourier Transformation)

中文名：快速傅里叶离散变换

作用 : 以$O(nlogn)$的复杂度计算多项式乘法(你以为呢?Of course more than that!)。

大家在学多项式乘法的时候,是不是觉得拆括号特别麻烦。

比如说计算$(x^2+3x-1)*(2x^2+x-5)$

原式$=x^2(2x^2+x-5)+3x(2x^2+x-5)-(2x^2+x-5)$

$\quad\ \ \ =(2x^4+x^3-5x^2)+(6x^3+3x^2-15x)-(2x^2+x-5)$

$\quad\ \ \ =2x^4+x^3-5x^2+6x^3+3x^2-15x-2x^2-x+5$

$\quad\ \ \ =2x^4+(x^3+6x^3)+(3x^2-2x^2-5x^2)+(-x-15x)+5$

$\quad\ \ \ =2x^4+7x^3-4x^2-16x+5$

很复杂...

现在我们就要用计算机把两个多项式乘起来(所谓多项式问题)。

P.S:下面提及的多项式均只有一元,你可以认为只有$x$这一元。

为了表述方便,下面定义一些记号(请仔细阅读)：

$F(x)$表示一个多项式,简单的叫做“多项式$F$”。

$F(x)$是简便写法,比如我们设$F(x)=x^2+x+1$,以后我们提起$x^2+x+1$就不用那么啰嗦,直接说$F(x)$就好啦。

你也可以把它理解为函数,上面的$F(x)=x^2+x+1$

那么$F(5)=5^2+5+1=31$,非常和谐。

系数(参数)

这里有一个n次多项式$F(x)$

差不多长成这样：$a*x^n+b*x^{n-1}+c*x^{n-2}+...$

其中$a,b,c...$是参数,因为他们在系数的位置上,所以也叫系数.

用不同的字母来表示系数很烦,我们就用数组。

通常把$F(x)$的$n$次项系数称作$F[n]$。

也即$F(x)=\sum^{n}_{i=0}F[i]x^i$

乘法的本质(卷积)

现在如果让你把两个$n$次多项式$F(x)$和$P(x)$乘起来,你会怎么写程序？

简单啦！

设$C=A*B$(多项式).

$C[k]=\sum\limits_{i=0}^kA[i]B[k-i]$

理解:想要乘出$x^k$,需要$A$的$x^i$项和$B$的$x^{k-i}$项。

也就是说$A[i]B[k-i]$乘起来之后,他们后面的未知数就变成了$x^k$,所以要往$C[k]$贡献。

也可以写做等价的$C[k]=\sum\limits_{i+j==k}A[i]B[j]$(不懂没关系,看代码你就懂了)

形为$C[k]=\sum\limits_{i⊕j==k}A[i]B[j]$的式子称为卷积,其中$⊕$为某种运算。

那么你可能观察到了,多项式乘法就是加法卷积。

(后面我们还会学习到其他的卷积)

多项式乘法拥有交换律结合律分配率什么的,就不多说了……

亮出模板题

暴力卷积Code(用于上述模板题,44'):